Dynamic Programming

Dynamic programming is a technique used in solving problems bottom-up (or top-down), and use solutions from overlapping subproblems to build up our larger solutions. In this example, if we figure out that we can make a small 2x2 grouping, can we use that to form larger groupings?

Kadane's Algorithm in 1D

Kadane's algorithm finds the largest subarray in an array containing numbers in O(N) time with O(1) space. For example:

[3, 6, -1, 3, -6, -7, 3, 15, -432, 2]
Largest subarray => [3, 15] => 3+15 => 18

This can be computed efficient by taking into consideration the following facts which are at the core of Kadane's algorithm:

  • Start iterating through the array
  • Keep a cumulative sum
  • If, so far, our sum is positive, we should keep our elements
  • If we get a negative number, then we should start over

This is efficient, because at each iteration of Kadane's algorithm, we don't have to look back, and we use constant memory. A naive solution would have a complexity of O(2^N)

Relating Kadane's Algorithm to Karnaugh Maps

If we can extend Kadane's Algorithm to 2D, and instead find the largest submatrices such that all rows/columns are filled, we would solve our problem. How can this be solved? First, consider the Karnaugh Map is a grid of 0's and 1's. From before, we know that it is a filled matrix if and only if the sum is equal to width * height.

Hence, we need to extend Kadane's algorithm to 2D, taking note of the perfectly filled matrices.

Extending Algorithm to 2D

The following describes the algorithm, which takes O(N^2*M) time:

  1. Store the cumulative sums of all columns in the matrix. That is, the top-most row should contain just that item, and the row below should contain that item plus the item at its row/columns
  2. Start iterating through from the top row to the bottom row, called x1
  3. Start another loop, which iterates from x1 to the bottom as well, called x2
  4. Subtract, for all columns, the difference in height between x2 and x1. This is the sum using the prefix sums array
  5. For the produced difference array, run 1D Kadane's algorithm
  6. When runnning Kadane's algorithm, do not include results who have different consecutive values in the 1D array. These potential matrices have holes with 0. Also ignore cases of illegal sizes.

The end result contains the largest matrix possible. To store the results, you can store them in a data-structure like a heap and sort based on Math.abs(x1-x2) * Math.abs(y1-y2)

For example:

[0, 1, 0, 0      =>         [0, 1, 0, 0
 1, 1, 1, 1      =>          1, 2, 1, 1 
 0, 1, 1, 1      =>          1, 3, 2, 1
 0, 0, 1, 0]     =>          1, 3, 3, 1]

Following the algorithm previously illustrated, we first store the cumulative sums going down the columns. We then iterate through the indices with our x1 and x2 pointers.

So we first get [0, 1, 0, 0] as our array, with x1 = 0 and x2 = 1, which we consider 1 to be the largest. We know it is 1x1 in size because (x2-x1=1) and we cover a range of 1.

We then extend this further, increasing x2 until we get to 4, then increment x1 by one and repeat, resulting in O(N^2) time before invoking 1D Kadane's algorithm, which takes O(N) time.

When we get x1=1 and x2=3, we have [0, 2, 2, 1], which gives us [2, 2] with x2-x1=2, hence we have our maximum here being a grouping of 4.

Storing Results

We can have several algorithms for storing the results. The easiest way is to store another 2D grid with the maximum pairing so far that encompasses that specific grid cell. If your new candidate is larger and it satisfies, you can set that grid. Else, you can discard it unless another cell requires it to be occupied. This will result in O(N*M) memory, which is optimal.